from typing import *
from collections import deque


# https://leetcode.cn/problems/QA2IGt/submissions/
# 剑指 Offer II 113. 课程顺序
# 拓扑排序
class Solution:

    def findOrder(self, numCourses: int,
                  prerequisites: List[List[int]]) -> List[int]:
        n = numCourses
        nts = [[] for _ in range(n)]
        ins = [0] * n
        for a, b in prerequisites:
            nts[b].append(a)
            ins[a] += 1
        q = deque()
        for i in range(n):
            if ins[i] == 0:
                q.append(i)
        ans = []
        while q:
            c = q.pop()
            ans.append(c)
            for nt in nts[c]:
                ins[nt] -= 1
                if ins[nt] == 0:
                    q.append(nt)

        return ans if len(ans) == n else []